1. Field of the Invention
This invention relates to network routing.
2. Related Art
In routing packets in a network, a router sometimes has a choice of more than one path to a selected destination. When there is more than one path, there is a possibility that the router can distribute packet traffic among the paths, so as to reduce the aggregate packet traffic load on any one individual path. This concept is known in the art of network routing as "load sharing."
One problem that has arisen in the art is that sharing packet traffic among more than one such path can result in out-of-order arrival of packets at the destination device (or at an intermediate device on both paths to the destination device). Out-of-order arrival of packets is generally undesirable, as some protocols rely on packets arriving in the order they were sent.
Accordingly, it would be desirable to share packet traffic load among more than one such path, while maintaining the order in which the packets were sent in all cases where order matters. The invention provides load-sharing that is preferably performed on a per-flow basis, but possibly on a per-packet basis. A "flow" is a sequence of packets transmitted between a selected source and a selected destination, generally representing a single session using a known protocol. Each packet in a flow is expected to have identical routing and access control characteristics.
Flows are further described in detail in the following patent applications:
U.S. application Ser. No. 08/581,134, titled "Method For Traffic Management, Traffic Prioritization, Access Control, and Packet Forwarding in a Datagram Computer Network", filed Dec. 29, 1995, in the name of inventors David R. Cheriton and Andreas V. Bechtolsheim, assigned to Cisco Technology, Inc., attorney docket number CIS-019; PA1 U.S. application Ser. No. 08/655,429, titled "Network Flow Switching and Flow Data Export", filed May 28, 1996, in the name of inventors Darren Kerr and Barry Bruins, and assigned to Cisco Technology, Inc., attorney docket number CIS-016; and PA1 U.S. application Ser. No. 08/771,438, titled "Network Flow Switching and Flow Data Export", filed Dec. 20, 1996, in the name of inventors Darren Kerr and Barry Bruins, assigned to Cisco Technology, Inc., attorney docket number CIS-017. PA1 PCT International Application PCT/US 96/20205, titled "Method For Traffic Management, Traffic Prioritization, Access Control, and Packet Forwarding in a Datagram Computer Network", filed Dec. 18, 1996, in the name of inventors David R. Cheriton and Andreas V. Bechtolsheim, and assigned to Cisco Technology, Inc., attorney docket number CIS-019 PCT; and PA1 U.S. application Ser. No. 08/655,429, Express Mail Mailing No. EM053698725US, titled "Network Flow Switching and Flow Data Export", filed Jul. 2, 1997, in the name of inventors Darren Kerr and Barry Bruins, assigned to Cisco Technology, Inc.
These patent applications are collectively referred to herein as the "Netflow Switching Disclosures." Each of these applications is hereby incorporated by reference as if fully set forth herein.
However, one problem with sharing packet traffic load among more than one such path, whether on a per-packet basis or on a per-flow basis, is that the number of packets or the number of flows may not be evenly divisible by the number of such paths. In fact, with the number of packets or the number of flows continually changing, it would be difficult at best to maintain an even distribution of packets or flows into the number of such paths.
One response to this problem is to provide a hash function, to pseudo-randomly assign each packet or each flow to a hash value, and to share the packet traffic load among the paths in response to the hash value (such as by associating each hash table entry with a selected path). While this technique achieves the purpose of sharing the packet traffic load among more than one path to the destination, it has the drawback that packet traffic load is typically not evenly divided, particularly when the number of such paths is not a power of two.
For example, if there are three bits of hash value, thus providing eight possible hash values in all, but there are only five paths to the destination (or the weighted sum of desirable path loads is a multiple of five), the first five hash values would be evenly distributed among the paths, but the remaining three hash values would be unevenly distributed to three of the five possible paths.
One response to this problem is to select a hash value with more bits, and thus with more possible values, so as to more evenly distribute packets or flows among the possible paths. While this method achieves the purpose of evenly distributing packet traffic load, it has the drawback of requiring a relatively large amount of memory for the associated hash table, an amount of memory which is relatively larger as the amount of desired load imbalance is reduced.
Accordingly, it would be advantageous to provide a method and system in which packet traffic can be relatively evenly divided among a plurality of possible paths, without requiring a relatively large amount of memory. This advantage is achieved in an embodiment of the invention which provides a hash value with a relatively large number of bits, but which provides for processing that hash value using the number of possible paths so as to associate that hash value with a selected path using a table having a relatively small number of entries. The processing can be performed rapidly in hardware using a relatively small amount of circuitry.